406D - Hill Climbing - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

#define int long long

struct Point {
  int x, y;

  Point() {}
  Point(int _x, int _y): x(_x), y(_y) {}
};

inline int ori(Point a, Point b, Point c) {
  Point ba = {a.x - b.x, a.y - b.y};
  Point bc = {c.x - b.x, c.y - b.y};
  int cross =  (ba.x * bc.y - ba.y * bc.x);

  if (cross == 0) return 0;
  if (cross > 0) return +1;
  return -1;
}

const int N = 1e5 + 5;

int n;
Point a[N];
vector<int> g[N];
int par[N][20], dep[N];

void dfs(int u) {
  for (int v: g[u]) {
    par[v][0] = u;
    dep[v] = dep[u] + 1;

    for (int i = 1; (1 << i) <= n; ++i) {
      par[v][i] = par[par[v][i - 1]][i - 1];
    }

    dfs(v);
  }
}

int lca(int u, int v) {
  if (dep[u] > dep[v]) swap(u, v);
  int d = dep[v] - dep[u];
  for (int i = 0; (1 << i) <= d; ++i) {
    if (d >> i & 1) v = par[v][i];
  }
  if (u == v) return u;

  for (int i = 17; ~i; --i) {
    if (par[u][i] != par[v][i]) {
      u = par[u][i];
      v = par[v][i];
    }
  }

  return par[u][0];
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;

  vector<int> hull;
  hull.push_back(n);
  for (int i = n - 1, sz = 1; i; --i, ++sz) {
    while (sz >= 2 && ori(a[i], a[hull[sz - 1]], a[hull[sz - 2]]) < 0) {
      hull.pop_back();
      sz -= 1;
    }

    g[hull.back()].push_back(i);
    hull.push_back(i);
  }

  dfs(n);
  int m; cin >> m;
  while (m--) {
    int u, v; cin >> u >> v;
    cout << lca(u, v) << ' ';
  }
}